package lee.study.BinaryTree.BinaryTreeTest;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                '}';
    }

    public class TestDemo1105 {
        public TreeNode buildTree() {
            TreeNode A = new TreeNode(10);
            TreeNode B = new TreeNode(20);
            TreeNode C = new TreeNode(11);
            TreeNode D = new TreeNode(22);
            TreeNode E = new TreeNode(33);
            TreeNode F = new TreeNode(44);
            TreeNode G = new TreeNode(55);
            TreeNode H = new TreeNode(66);
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            D.left = H;
            return A;
        }

        //输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
        public TreeNode prev = null;//定义前驱

        public void ConvertChild(TreeNode pRootOfTree) {
            if (pRootOfTree == null) return;
            ConvertChild(pRootOfTree.left);
            pRootOfTree.left = prev;//修改左边节点
            prev = pRootOfTree;
            if (prev != null) {//如果为空，则是第一次
                prev.right = pRootOfTree;//将prev的后继与pRootOfTree相连接
            }
            ConvertChild(pRootOfTree.right);
        }

        public TreeNode Convert(TreeNode pRootOfTree) {
            if (pRootOfTree == null) return null;
            ConvertChild(pRootOfTree);
            TreeNode head = pRootOfTree;
            while (head.left != null) {
                head = head.left;
            }
            return head;
        }


        //5.根据一棵树的前序遍历和中序遍历来构建二叉树。
        public int preIndex = 0;//每次递归的头结点，第一次为preOrder[preIndex];

        public TreeNode BuildTreeChild(int[] preOrder, int[] inOrder, int inbegin, int inend) {
            if (inbegin > inend) {
                return null;//当走到这一步时，说明没有节点了
            }
            TreeNode root = new TreeNode(preOrder[preIndex]);
            //找到当前根节点在中序遍历inOreder[]当中的位置
            int rootIndex = findIndexOfInorder(inOrder, inbegin, inend, preOrder[preIndex]);
            preIndex++;
            if (rootIndex == -1) return null;
            root.left = BuildTreeChild(preOrder, inOrder, inbegin, rootIndex - 1);
            root.right = BuildTreeChild(preOrder, inOrder, rootIndex + 1, inend);
            return root;
        }

        public int findIndexOfInorder(int[] inorder, int inbegin, int inend, int val) {
            //找到中序遍历中的头结点的索引
            for (int i = inbegin; i <= inend; i++) {
                if (inorder[i] == val) {
                    return i;
                }
            }
            return -1;
        }

        public TreeNode buildTree(int[] preOrder, int[] inOrder) {//前序和中序
            if (preOrder == null || inOrder == null) return null;
            if (preOrder.length <= 0 || inOrder.length <= 0) return null;
            return BuildTreeChild(preOrder, inOrder, 0, preOrder.length);
        }


        public int postIndex;

        public TreeNode BuildTreeChild1(int[] inOrder, int[] postOrder, int inend, int inbegin) {
            if (inbegin > inend) return null;
            TreeNode root = new TreeNode(postOrder[postIndex]);

            int rootIndex = findIndexOfInorder1(inOrder, inbegin, inend, postOrder[postIndex]);
            postIndex--;
            if (rootIndex == -1) return null;

            root.right = BuildTreeChild1(inOrder, postOrder, inend, postIndex + 1);
            root.left = BuildTreeChild1(inOrder, postOrder, postIndex - 1, inbegin);

            return root;
        }

        public int findIndexOfInorder1(int[] postorder, int inbegin, int inend, int val) {
            for (int i = inbegin; i <= inend; i++) {
                if (postorder[i] == val) {
                    return i;
                }
            }
            return -1;
        }

        public TreeNode buildTree1(int[] inOrder, int[] postOrder) {//中序和后序
            if (inOrder == null || postOrder == null) return null;
            if (inOrder.length <= 0 || postOrder.length <= 0) return null;
            postIndex = inOrder.length - 1;
            return BuildTreeChild1(inOrder, postOrder, 0, inOrder.length);
        }

        // 根据二叉树创建字符串
        public void tree2strChild(TreeNode t, StringBuffer sb) {
            if (t == null) return;
            sb.append(t.val);
            if (t.left==null){//左边为空
                if (t.right==null){//左边为空右边也为空
                    return;
                }else{//左边为空右边不为空
                    sb.append("()");
                }
            }else{//左边不为空
                sb.append('(');
                tree2strChild(t.left,sb);
                sb.append(')');
            }

            if (t.right==null){//右边为空
                return;
            }else {//右边不为空
                sb.append('(');
                tree2strChild(t.right,sb);
                sb.append(')');
            }
        }

        public String tree2str(TreeNode t) {
        StringBuffer sb=new StringBuffer();
        return sb.toString();
        }
    }


}
